"""
17.
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
"""

from typing import List


class Solution:
    # 建立数字到字符串的映射
    mapping = {
        '0': ' ',
        '1': '',
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    def generate_combination_string(self, digits: str, index: int, s: str, collector: List):
        if index == len(digits):
            collector.append(s)
            return
        
        char = digits[index]
        letters = self.mapping[char]
        for letter in letters:
            self.generate_combination_string(
                digits, index+1, s+letter, collector)

        return

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        res = []
        self.generate_combination_string(digits, 0, "", res)
        return res


def test():
    obj = Solution()
    res = obj.letterCombinations("23")
    print(res)


if __name__ == "__main__":
    test()
